package test.day02;

import java.util.*;

public class ThreeSumZero {
	public static void main(String[] args) {
		ThreeSumZero solution = new ThreeSumZero();
		int[] nums = new int[]{-1,0,1,2,-1,-4};
		long start = System.currentTimeMillis();
		List<List<Integer>> lists = solution.threeSumOther1(nums);
		long end = System.currentTimeMillis();
		System.out.println("操作耗时："+(end-start)+"ms");
		System.out.println(Arrays.deepToString(lists.toArray()));
	}

	public List<List<Integer>> threeSum(int[] nums) {
		if(nums.length < 3) {
			return new ArrayList<>();
		}
		//首先对数组排序
		Arrays.sort(nums);
		List<List<Integer>> result = new ArrayList<>();
		int left = 0;
		int right = nums.length-1;
		int mid = (right-left)/2;
		boolean isBeforeSame = false;
		while (mid - 1 >= left && mid + 1 <= right) {
			if(nums[left] + nums[right] + nums[mid] == 0) {
				if(!isBeforeSame) {
					List<Integer> data = new ArrayList<>();
					data.add(nums[left]);
					data.add(nums[mid]);
					data.add(nums[right]);
					result.add(data);
				}
				isBeforeSame = true;
				if (right-mid > mid-left) {
					right--;
				}else {
					left++;
				}
				continue;
			}else if (nums[left] + nums[right] + nums[mid] > 0) {
				isBeforeSame = false;
				if(mid - 1 > left) {
					mid--;
					continue;
				}
			}else {
				isBeforeSame = false;
				if(mid + 1 < right) {
					mid++;
					continue;
				}
			}
			if (mid + 1 == right && mid - 1 > left) {
				left++;
				continue;
			}
			if(mid - 1 == left && mid + 1 < right) {
				right--;
				continue;
			}
			if(mid - 1 == left && mid + 1 == right) {
				break;
			}
		}
		return result;
	}

	public List<List<Integer>> threeSumOther(int[] nums) {

		List<List<Integer>>ans=new ArrayList<>();
		if(nums.length<3) {
			return ans;
		}
		Set<List<Integer>> set=new HashSet<>();
		Arrays.sort(nums);
		for(int i=0;i<nums.length-1;i++){
			int left=i;
			int mid=i+1;
			int right=nums.length-1;
			while(mid<right) {
				if(nums[mid]+nums[right]+nums[left]>0){
					right--;
				} else if(nums[mid]+nums[right]+nums[left]<0){
					mid++;
				} else{
					List<Integer>list=new ArrayList<>();
					list.add(nums[left]);
					list.add(nums[mid]);
					list.add(nums[right]);
					set.add(list);
					right--;
					mid++;//找到一组答案后同时收缩,继续搜索
				}
			}
		}
		for(List<Integer>list:set){
			ans.add(list);
		}
		return ans;
	}


	public List<List<Integer>> threeSumOther1(int[] nums) {
		List<List<Integer>> result = new ArrayList<>(nums.length);
		if(nums.length < 3) {
			return result;
		}
		Set<List<Integer>> set = new HashSet<>();
		Arrays.sort(nums);
		for (int i = 0; i < nums.length - 1; i++) {
			int left = i;
			int right = nums.length - 1;
			int mid = i + 1;
			while(mid < right) {
				int sum = nums[left] + nums[mid] + nums[right];
				if (sum > 0) {
					// 三数之和>0,缩小右边最大的数字
					right--;
				} else if (sum < 0) {
					// 三数之和<0,增加左边的数字
					mid++;
				} else {
					// equal=0，left++, right--;
					List<Integer> tmpList = new ArrayList<>();
					tmpList.add(nums[left]);
					tmpList.add(nums[mid]);
					tmpList.add(nums[right]);
					set.add(tmpList);
					mid++;
					right--;
				}
			}
		}
		for (List<Integer> s : set) {
			result.add(s);
		}
		return result;
	}
}
